package graph;

/*
 *@description 被围绕的区域
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_130 {



    /**
     * @description 解题思路：从边界开始BFS
     * @author hkfan
     * @time 2025/6/18 15:56
     */
    public void solve(char[][] board) {
        int m = board.length,n=board[0].length;
        int[][] grid;
        //从边界开始BFS
        for (int i = 0; i < m; i++) {
            if (board[i][0]=='O'){
                update(board,i,0,'#');
            }
        }
        for (int i = 0; i < m; i++) {
            if (board[i][n-1]=='O'){
                update(board,i,n-1,'#');
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j]=='O'){
                update(board,0,j,'#');
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[m-1][j]=='O'){
                update(board,m-1,j,'#');
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j]=='#'){
                    board[i][j]='O';
                } else if (board[i][j]=='O') {
                    board[i][j]='X';
                }
            }
        }
    }

    private void update(char[][] board, int i, int j,char x) {
        int m = board.length,n=board[0].length;
        if (i<0 ||j<0 ||i>=m ||j>=n){
            return;
        }

        if (board[i][j]=='O'){
            board[i][j]=x;
            if (j<n-1){
                update(board,i,j+1,x);
            }
            if (i<m-1){
                update(board,i+1,j,x);
            }
            if (j>0){
                update(board,i,j-1,x);
            }
            if (i>0){
                update(board,i-1,j,x);
            }
        }
    }
}
